package com.wmx.datastructuresandalgorithms;


import java.util.*;

public class SingleLinkedList {
    private int size;//链表节点数
    private Node head; //头节点、
    public SingleLinkedList(){
        this.size = 0;
        this.head =null;
    }



    //链表的每个
    class Node{
        private Object data;
        private Node next ;
        Node(Object data){
            this.data = data;
        }

    }

    //重头部添加节点
    private Object addNode(Object object){
        Node newNode = new Node(object);
        if(size==0){
           head = newNode;
        }else {
            newNode.next =head;
            head = newNode;

        }

        size++;
        return object;
    }


    //从尾部添加节点
    private Object addRearNode(Object object){
        Node newNode = new Node(object);
        Node temp = head;
        if(size==0){
            head = newNode;
        }else {
           while (true){
               if(temp.next == null){
                   break;
               }
             temp =  temp.next;
           }

           temp.next = newNode;

        }
        size++;
        return object;
    }
    //查看头节点

    public Node getHead() {
        return head;
    }

    //删除节点
    public void  remove(){
       if(head == null)
           throw new  IllegalArgumentException("链表为空");

       Node newNode =head;
       while (newNode.next != null){
           if(newNode.next.next==null){
               break;
           }
           newNode = head.next;
       }

       newNode.next=null;
       size--;
    }


    //单向链表反转

    /**
     * 思路：
     * ①定义一个新头
     * ②：从头到尾遍历链表，并将其节点放在新头的最前端和后端。
     * 提交时间	提交结果	执行用时	内存消耗	语言
      几秒前	通过	1 ms	36.2 MB	Java
     *
     * @param headNode
     */
    public void reversal(Node headNode){
        if(headNode == null || headNode.next==null){
            return;
        }
        //需要反转的链表头
        Node newNode = headNode;

        Node cur = null;

        //新头
        Node newHead =null ;


        while (true){

             cur = newNode.next;
             newNode.next = newHead;
             newHead = newNode;
             newNode = cur;
            if(newNode.next == null){
                cur.next = newHead;
                newHead = cur;
                break;
            }
        }
        head = newHead;
    }



    /*
    * 思路 ： 循环链表 ，将链表装入到stack中 ，在起初，加入链表
    * 怎样循环stack（栈中的元素）
    * 提交时间	提交结果	执行用时	内存消耗	语言
     几秒前	通过	4 ms	36.5 MB	Java
    * */

    public Node reversalOne(Node headNode){
        Stack<Node> stack = new Stack();
        if(headNode==null||headNode.next == null){
            return  headNode;
        }

        while (true){
            stack.push(headNode);
            if(headNode.next == null) {
                break;
            }
            headNode = headNode.next;
        }

        Node newHeadNode = new Node(0);
        Node current = newHeadNode;

        while (!stack.isEmpty()){
            Node temp = stack.pop();
            current.next = temp;
            current =temp;
        }
        current.next = null;
        return newHeadNode.next;
    }


    public  void  display(Node headNode){
        System.out.printf("[");
        while (true){
            if(headNode.next == null){
                System.out.printf(headNode.data+"]");
                break;
            }else {
                System.out.printf(headNode.data+"—>");
            }
            headNode = headNode.next;
        }

    }


    public void del(Node headNode){
        //①对链表头的校验 判断头是否为空 或 头是否包含下一个节点
        // ②：遍历链表，判断节点是否为尾节点，将尾巴的上一个节点的next指向null
        if(headNode == null){
            System.out.printf("链表为空");
        }

        while (headNode.next != null){
            if(headNode.next.next == null){
                headNode.next =null;
                break;
            }
            headNode = headNode.next;
        }

    }




    public Node sortList(Node head) {
        if (head==null||head.next==null){
            return head;
        }

        List<Node> list = new ArrayList<Node>();

        Node cure = head ;
        while (true){
            list.add(cure);
            if(cure.next == null){
                break;
            }

            cure = cure.next;
        }

        Collections.sort(list, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return (int)o1.data-(int)o2.data;
            }
        });
        Node first = new Node(0);
        cure = first;
        for (Node node: list) {
             cure.next = node;
             cure = node;
        }
        cure.next =null;
        return first.next;
    }

    public static void main(String[] args) {
       /* SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addRearNode(2);
        singleLinkedList.addRearNode(44);
        singleLinkedList.addRearNode(21);
        singleLinkedList.addRearNode(13);
        singleLinkedList.display(singleLinkedList.getHead());
        Node newHead =  singleLinkedList.reversalOne(singleLinkedList.getHead());
        singleLinkedList.display(newHead);*/
       // singleLinkedList.display(singleLinkedList.getHead());

        // singleLinkedList.sortList(singleLinkedList.getHead()) ;
       // singleLinkedList.display(singleLinkedList.sortList(singleLinkedList.getHead()));


       Stack<Integer> stack =new Stack();
       stack.push(1);
       stack.push(2);
       stack.push(2);
       stack.push(5);
       while (!stack.isEmpty()){
           System.out.println(stack.pop());
       }




    }
}
